﻿using System;
using System.Collections.Generic;
using System.Text;

namespace ANLP
{
    public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>, IList<KeyValuePair<TKey, TValue>>
    {
        public SortedList()
            : this(Comparer<TKey>.Default)
        {

        }

        public SortedList(IComparer<TKey> comparer)
        {
            this.comparer = comparer;
            keys = new List<TKey>();
            values = new List<TValue>();
        }

        IList<TKey> keys;
        IList<TValue> values;
        private IComparer<TKey> comparer;

        #region IDictionary<TKey,TValue> Members

        public void Add(TKey key, TValue value)
        {
            Add(new KeyValuePair<TKey, TValue>(key, value));
        }

        public bool ContainsKey(TKey key)
        {
            return keys.Contains(key);
        }

        public ICollection<TKey> Keys
        {
            get { return keys; }
        }

        public bool Remove(TKey key)
        {
            int index = keys.IndexOf(key);
            if (index != -1)
            {
                keys.RemoveAt(index);
                values.RemoveAt(index);
                return true;
            }
            return false;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int index = keys.IndexOf(key);
            if (index != -1)
            {
                value = values[index];
                return true;
            }
            value = default(TValue);
            return false;
        }

        public ICollection<TValue> Values
        {
            get { return values; }
        }

        public TValue this[TKey key]
        {
            get
            {
                int index = keys.IndexOf(key);
                if (index == -1)
                    throw new KeyNotFoundException();
                return values[index];
            }
            set
            {
                int index = keys.IndexOf(key);
                if (index == -1)
                {
                    Add(key, value);
                }
                else
                {
                    values[index] = value;
                }
            }
        }

        #endregion

        #region ICollection<KeyValuePair<TKey,TValue>> Members

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            int index = FindIndexForKey(item.Key);


            keys.Insert(index, item.Key);
            values.Insert(index, item.Value);
        }

        private int FindIndexForKey(TKey tKey)
        {
            int previousComparison = -1;
            for (int i = 0; i < keys.Count; i++)
            {
                if (i == 0)
                {
                    if ((previousComparison = comparer.Compare(tKey, keys[i])) == -1)
                        return 0;
                }
                else
                {
                    if (comparer.Compare(tKey, keys[i]) == previousComparison)
                        continue;
                    else
                        return i;
                }
            }
            return keys.Count;
        }

        public void Clear()
        {
            keys.Clear();
            values.Clear();
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            int index = keys.IndexOf(item.Key);
            if (index == -1)
                return false;
            return EqualityComparer<TValue>.Default.Equals(values[index], item.Value);
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public int Count
        {
            get { return keys.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            int index = keys.IndexOf(item.Key);
            if (index == -1)
                return false;
            keys.RemoveAt(index);
            values.RemoveAt(index);
            return true;
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Members

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            for (int i = 0; i < keys.Count; i++)
            {
                yield return new KeyValuePair<TKey, TValue>(keys[i], values[i]);
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region IList<KeyValuePair<TKey,TValue>> Members

        int IList<KeyValuePair<TKey, TValue>>.IndexOf(KeyValuePair<TKey, TValue> item)
        {
            int index = keys.IndexOf(item.Key);
            if (index == -1)
                return -1;
            return values.IndexOf(item.Value) == index ? index : -1;
        }

        public void Insert(int index, KeyValuePair<TKey, TValue> item)
        {
            keys.Insert(index, item.Key);
            values.Insert(index, item.Value);
        }

        public void RemoveAt(int index)
        {
            keys.RemoveAt(index);
            values.RemoveAt(index);
        }

        public KeyValuePair<TKey, TValue> this[int index]
        {
            get
            {
                return new KeyValuePair<TKey, TValue>(keys[index], values[index]);
            }
            set
            {
                keys[index] = value.Key;
                values[index] = value.Value;
            }
        }

        #endregion
    }
}
